package leo.mystudy.leetcode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author leo
 * @version 1.0.0
 * @description 给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
 * <p>
 * 请你找出并返回只出现一次的那个数。
 * <p>
 * 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,1,2,3,3,4,4,8,8]   8、4、2、1
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: nums =  [3,3,7,7,10,11,11]   6、3、1
 * 输出: 10
 *  
 * <p>
 * 提示:
 * <p>
 * 1 <= nums.length <= 105
 * 0 <= nums[i] <= 105
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @create 2022/2/14 11:29
 */
public class No540SingleNonDuplicate {
    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while ((mid = (left + right + 1) / 2) >= 1) {
            int mv = nums[mid];
            int diff = right - left;
            if (diff == 0) {
                return mv;
            }
            int pv = nums[mid - 1];
            int nv = nums[mid + 1];
            if (diff == 2) {
                if (mv == pv) {
                    return nv;
                } else {
                    return pv;
                }
            }
            if (mv != pv && mv != nv) {
                // 如果当前中值不和左右相等，返回当前值
                return mv;
            }
            if ((diff / 2) % 2 == 0) {
                // 如果切分后半数为偶数个
                if (mv == pv) {
                    right = mid;
                } else {
                    left = mid;
                }
            } else {
                // 如果切分后半数为奇数个
                if (mv == pv) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return nums[mid];
    }

    public static void main(String[] args) {
        int[] nums = {1,1,2};
        System.out.println(new No540SingleNonDuplicate().singleNonDuplicate(nums));
    }

}
